class DBSCAN:
    def __init__(self, eps=0.5, min_samples=5):
        """
        初始化 DBSCAN 参数
        :param eps: 两点间的最大距离，用于定义邻域
        :param min_samples: 成为核心点的最小点数（包括自身）
        """
        self.eps = eps
        self.min_samples = min_samples

    def fit_predict(self, X):
        """
        对数据进行聚类
        :param X: 输入数据 (n_samples, n_features)
        :return: 聚类标签列表 (n_samples,)
        """
        n_samples = len(X)
        labels = [-1] * n_samples  # 初始化标签，-1 表示未分配
        cluster_id = 0

        for i in range(n_samples):
            if labels[i] != -1:  # 已处理点跳过
                continue

            # 获取点 i 的邻域
            neighbors = self._region_query(X, i)

            # 不满足 min_samples 的点标记为噪声点
            if len(neighbors) < self.min_samples:
                labels[i] = -1  # -1 表示噪声
                continue

            # 创建新簇并扩展邻域
            self._expand_cluster(X, labels, i, neighbors, cluster_id)
            cluster_id += 1

        return labels

    def _region_query(self, X, point_idx):
        """
        查找某点的邻域点
        :param X: 输入数据
        :param point_idx: 当前点的索引
        :return: 邻域点的索引列表
        """
        neighbors = []
        for i in range(len(X)):
            # 手动计算欧几里得距离
            distance = self._euclidean_distance(X[point_idx], X[i])
            if distance <= self.eps:  # 距离小于 eps 的为邻域点
                neighbors.append(i)
        return neighbors

    def _euclidean_distance(self, p1, p2):
        """
        手动计算两点间的欧几里得距离
        :param p1: 点 1 坐标
        :param p2: 点 2 坐标
        :return: 欧几里得距离
        """
        return sum((x1 - x2) ** 2 for x1, x2 in zip(p1, p2)) ** 0.5

    def _expand_cluster(self, X, labels, point_idx, neighbors, cluster_id):
        """
        扩展新簇，标记点所属的聚类
        :param X: 输入数据
        :param labels: 聚类标签
        :param point_idx: 当前点的索引
        :param neighbors: 当前点的邻域点索引
        :param cluster_id: 当前簇的 ID
        """
        queue = list(neighbors)  # 将邻域点加入队列
        labels[point_idx] = cluster_id

        while queue:
            current_idx = queue.pop(0)  # 获取队列中的一个点

            # 如果当前点是未访问或噪声点
            if labels[current_idx] == -1:  # 之前标记为噪声
                labels[current_idx] = cluster_id

            if labels[current_idx] != -1:  # 已属于某簇的跳过
                continue

            labels[current_idx] = cluster_id  # 分配当前点到簇
            current_neighbors = self._region_query(X, current_idx)

            # 如果当前点也是核心点，合并其邻域到队列
            if len(current_neighbors) >= self.min_samples:
                queue.extend(current_neighbors)


# 测试 DBSCAN 的实现
if __name__ == "__main__":
    import random
    import matplotlib.pyplot as plt
    import matplotlib.cm as cm
    import matplotlib.colors as colors


    # 生成测试数据
    def make_blobs(n_samples=300, centers=4, cluster_std=0.5, random_state=None):
        random.seed(random_state)
        blobs = []
        labels = []
        for i in range(centers):
            center = [random.uniform(-10, 10) for _ in range(2)]
            for _ in range(n_samples // centers):
                point = [random.gauss(center[j], cluster_std) for j in range(2)]
                blobs.append(point)
                labels.append(i)
        return blobs, labels

    X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.5, random_state=0)

    # print(type(X))
    # 使用自定义 DBSCAN
    dbscan = DBSCAN(eps=2, min_samples=6)
    labels = dbscan.fit_predict(X)
    # print(X)
    # print(labels)
    unique_labels = set(labels)
    # print(unique_labels)
    num_cluster = len(unique_labels)
    cmap = cm.tab10    # 使用tab10进行颜色映射
    norm = colors.Normalize(vmin=min(unique_labels), vmax=max(unique_labels))  # 归一化标签范围

    # 使用不同颜色绘制每个聚类的点
    for label in unique_labels:
        # 筛选当前标签的数据点
        label_points = [X[i] for i in range(len(X)) if labels[i] == label]
        
        # 提取 x 和 y 坐标
        x_coords = [p[0] for p in label_points]
        y_coords = [p[1] for p in label_points]
        # plt.scatter([x[0] for x in X], [x[1] for x in X], color=cmap(norm(label)), s=25, label=f'Cluster {label}')
        plt.scatter(x_coords, y_coords, color=cmap(norm(label)), s=25, label=f'Cluster {label}')

    # 可视化聚类结果
    
    plt.title("DBSCAN Clustering")
    plt.xlabel("Feature 1")
    plt.ylabel("Feature 2")
    plt.legend()
    # plt.colorbar(label="Cluster ID")
    plt.show()
